11 R: Recursion

11.1 Recursion

Recursion is a method of solving a problem by dividing it into smaller instances of the same problem. Recursion solves such problems by using functions that call themselves from within their own code. This forms a loop, where every time the function is called, it calls itself again and again. However, every time the function calls itself, it checks certain condition(s) which are the stopping condition(s). When such condition(s) are true the function will stop calling itself. These conditions are called the base case of the recursive function.

Every recursive function must have at least two cases:

1. Base case: This is the simplest case that can be answered directly, and the function does not call itself.

2. Recursive case: This is a relatively more complex case that cannot be answered directly, but can be described as a smaller instance of the same problem. In this case, the function calls itself to answer the smaller problem.

Below is an example, where we defined a function that computes the factorial of an integer by recursion.

factorial <- function(n) {
  
  # Base case
  if (n == 1) return(1)    
  
  # Recursive case
  return(n * factorial(n - 1)) 
}
factorial(5)

[1] 120

In the above example, the case \(n=1\) is the base case, where the function does not need to call itself, and returns 1. All other cases, where \(n>1\), and \(n \in \mathbb{Z}\) are recursive cases, where the function calls itself with a smaller instance of the same problem.

A recursive function must satisfy the following conditions:

There must be a case for all valid inputs.
There must be a base case that makes no recursive calls.
When the function makes a recursive call, it should be to a simpler instance and make forward progress towards the base case.

Example: Write a recursive function that returns the \(n^{th}\) term of the Fibonacci sequence, where \(n\) is an integer, and \(n>0\). In a Fibonacci sequence, each number is the sum of the preceding two numbers, and the sequence starts from \(0,1\). The sequence is as follows:

\(0, 1, 1, 2, 3, 5, 8, 13, 21, ...\)

fibonacci <- function(n) {
  # Base case
  if (n == 0 | n == 1) return(n)
  
  #Recursive case
  return(fibonacci(n - 1) + fibonacci(n - 2))  
}
#The function `fibonacci` prints the n+1th term of the fibonacci sequence when `n` is passed as an argument. Thus, we need to reduce `n` by 1 to print the nth term of the sequence. The function `nth_term` reduces `n` by 1 before passing `n` to the function `fibonacci()`.
nth_term <- function(N) {
  fibonacci(N - 1)
}
nth_term(7)

[1] 8

11.1.1 Practice exercise 1

Write a recursive function that computes the sum of squares of the first \(N\) natural numbers, where \(N\) is a parameter to the function.

squares <- function(N)
{
  
  # Base case
  if(N == 1)  return(1)
  
  # Recursive case
  return(N ** 2 + squares(N - 1))
}
squares(10)

11.1.2 Practice exercise 2

Write a function that counts the occurrence of digit \(k\) in a given integer \(n\) using recursion. The function has \(n\) and \(k\) as parameters.

freq_digits <- function(n, d) {
  if (n == 0) return(0)
  digit <- n %% 10
  n_int <- as.integer(n / 10)
  if (digit == d) return(1 + freq_digits(n_int, d))
  return(freq_digits(n_int, d))
}
freq_digits(8670800,0)

11.1.3 Practice exercise 3

Use recursion to write a function that accepts a word as an argument, and returns TRUE if the word is a palindrome, otherwise returns FALSE.

word<-'racecar'
palindrome <- function(word) {
  if(nchar(word) <= 1) return(TRUE)
  if(substr(word, 1, 1) == substr(word, nchar(word), nchar(word))) {
    palindrome(substr(word, 2, nchar(word) - 1))
  } else return(FALSE)
}
palindrome(word)

11.2 Recursion vs iteration

Recursion is typically used when the problem is naturally recursive (for e.g., generating a Fibonacci sequence), or the data is naturally recursive ( for e.g., filesystem). Recursive solutions can be easy to read and understand as compared to the corresponding iterative solution.

One downside of recursion is that it may take more space than an iterative solution. Building up a stack of recursive calls consumes memory temporarily, and the stack is limited in size, which may become a limit on the size of the problem that the recursive implementation can solve.